A storage system provides storage service relating to the organization of information on storage devices. The storage system may be configured to operate according to a client-server model of information delivery to allow many client systems to access shared resources, such as data containers, stored on the storage system. An application may reside on a client system connected over a network to a storage system, such as a controller provided by NetApp, Inc., of Sunnyvale, Calif., or it may reside on the storage system itself. In either implementation, the application sends requests for data to the storage system and the requested data are returned to the application by the storage system.
The storage system may retrieve the requested data from the storage device or from a memory, if the requested data are in the memory. Retrieving data from the memory is faster than retrieving data from the storage device, such as a disk. However, since the memory has size limitations, the storage system predicts what data might be needed before the request is made in order to have the data in the memory when the request arrives. The storage system may employ speculative read-ahead operations to retrieve data blocks that are likely to be requested by future client read requests. These “read-ahead” blocks are typically retrieved from a storage device and stored in memory (i.e., buffer cache) in the storage system, where each read-ahead data block is associated with a unique block number.
Read-ahead techniques are known to “prefetch” a predetermined number of data blocks that logically extend the read stream. For instance, when a client's read request retrieves a sequence of data blocks assigned to consecutively numbered block numbers, a read-ahead operation may be invoked to retrieve additional data blocks assigned to block numbers that further extend the sequence, even though these additional read-ahead blocks have not yet been requested by the client. Typically, the read-ahead operations are “triggered” when a read stream is detected to have done multiple sequential read operations. For example, suppose a read stream read block number 1, 2, 3, and 4 in one read operation, and then, sometime later, reads blocks 5, 6, 7, and 8. A read-ahead engine might predict that the next read operation will be for blocks 9, 10, 11, and 12, instructing the storage system to retrieve blocks 5 through 12.
While known read-ahead techniques work well in certain situations, they occasionally suffer from disadvantages. For example, some of read-ahead algorithms assume that the read stream length will be short, at least until proven otherwise. This causes the algorithms to undershoot, that is, to behave as if the stream is smaller than it actually is and does not predict data that could be profitably read. Also, known algorithms may request large amounts of data on the assumption that the read requests will always be sequential. This causes the algorithms to overshoot, i.e., to predict that the stream will be larger than it actually is, thereby causing the system to read a relatively large fixed number of read-ahead data blocks. The overshooting, in turn, consumes an excessive amount of buffer memory in the storage system. The resulting excessive memory usage, or “cache pollution,” may cause the storage system to consume memory and resources that are needed for other system operations, and consequently may negatively impact the system's performance. For example, such cache pollution may increase the latency of data retrieval from the buffer memory since the storage system has to search a large number of “in-core” buffers containing read-ahead data. Furthermore, the risk of prefetching too much data may cause other data, which is more valuable than the prefetched data, to be evicted from the cache.
Accordingly, what is needed is a technique for optimizing prefetching of read-ahead data blocks in the storage system.